Jump to content

Tennenbaum's theorem

From Wikipedia, the free encyclopedia

Tennenbaum's theorem, named for Stanley Tennenbaum who presented the theorem in 1959, is a result in mathematical logic that states that no countable nonstandard model of first-order Peano arithmetic (PA) can be recursive (Kaye 1991:153ff).

Recursive structures for PA

[edit]

A structure in the language of PA is recursive if there are recursive functions and from to , a recursive two-place relation <M on , and distinguished constants such that

where indicates isomorphism and is the set of (standard) natural numbers. Because the isomorphism must be a bijection, every recursive model is countable. There are many nonisomorphic countable nonstandard models of PA.

Statement of the theorem

[edit]

Tennenbaum's theorem states that no countable nonstandard model of PA is recursive. Moreover, neither the addition nor the multiplication of such a model can be recursive.

Proof sketch

[edit]

This sketch follows the argument presented by Kaye (1991). The first step in the proof is to show that, if M is any countable nonstandard model of PA, then the standard system of M (defined below) contains at least one nonrecursive set S. The second step is to show that, if either the addition or multiplication operation on M were recursive, then this set S would be recursive, which is a contradiction.

Through the methods used to code ordered tuples, each element can be viewed as a code for a set of elements of M. In particular, if we let be the ith prime in M, then . Each set will be bounded in M, but if x is nonstandard then the set may contain infinitely many standard natural numbers. The standard system of the model is the collection . It can be shown that the standard system of any nonstandard model of PA contains a nonrecursive set, either by appealing to the incompleteness theorem or by directly considering a pair of recursively inseparable r.e. sets (Kaye 1991:154). These are disjoint r.e. sets so that there is no recursive set with and .

For the latter construction, begin with a pair of recursively inseparable r.e. sets A and B. For natural number x there is a y such that, for all i < x, if then and if then . By the overspill property, this means that there is some nonstandard x in M for which there is a (necessarily nonstandard) y in M so that, for every with , we have

Let be the corresponding set in the standard system of M. Because A and B are r.e., one can show that and . Hence S is a separating set for A and B, and by the choice of A and B this means S is nonrecursive.

Now, to prove Tennenbaum's theorem, begin with a nonstandard countable model M and an element a in M so that is nonrecursive. The proof method shows that, because of the way the standard system is defined, it is possible to compute the characteristic function of the set S using the addition function of M as an oracle. In particular, if is the element of M corresponding to 0, and is the element of M corresponding to 1, then for each we can compute (i times). To decide if a number n is in S, first compute p, the nth prime in . Then, search for an element y of M so that

for some . This search will halt because the Euclidean algorithm can be applied to any model of PA. Finally, we have if and only if the i found in the search was 0. Because S is not recursive, this means that the addition operation on M is nonrecursive.

A similar argument shows that it is possible to compute the characteristic function of S using the multiplication of M as an oracle, so the multiplication operation on M is also nonrecursive (Kaye 1991:154).

Turing degrees of models of PA

[edit]

Jockush and Soare have shown there exists a model of PA with low degree.[1]

References

[edit]
  • Boolos, George; Burgess, John P.; Jeffrey, Richard (2002). Computability and Logic (4th ed.). Cambridge University Press. ISBN 0-521-00758-5.
  • Kaye, Richard (1991). Models of Peano arithmetic. Oxford University Press. ISBN 0-19-853213-X.
  • Kaye, Richard (Sep 2011). "Tennenbaum's Theorem for Models of Arithmetic". In Juliette Kennedy and Roman Kossak (ed.). Set theory, arithmetic, and foundations of mathematics - theorems, philosophies (PDF). Lecture Notes in Logic. Vol. 36. ISBN 9781107008045.
  • Tennenbaum, Stanley (1959). "Non-Archimedean models for arithmetic". Notices of the American Mathematical Society. 6: 270.
  1. ^ V. Harizanov, "Chapter 1: Pure Computable Model Theory, in Handbook of Recursive Mathematics, edited by Yu. L. Ershov, S. S. Goncharov, A. Nerode, J. B. Remmel (1998, Elsevier). Chapter 1, p.13